The present invention relates to digital signal processing, and more particularly, to high speed multiplying and adding circuits particularly suited for calculating the dot product of large dimensional vectors.
Almost all digital signal processing algorithms involve the calculation of the dot product of vectors having a length greater than sixty-four bits. For example, such calculations are required in performing convolutions, discrete Fourier transforms, correlations and linear transforms.
Conventionally, the dot product of vectors A and B is computed by sequentially multiplying the components of A and B together and adding the same. On a general purpose digital computer this involves programming a loop. The time required to compute the dot products of vector A and B is a linear function of the size N of each vector. Substantial computational delays can result if N is large. If the vector B is held fixed, the computational delay becomes even more pronounced.
Heretofore digital systems have been provided for multiplying and adding at high speeds. See for example U.S. Pat. Nos. 4,369,500; 4,153,938; 4,142,242; 4,135,249; 4,031,377; 3,752,971; 3,691,359; 3,670,956; 3,372,269 and 3,163,749. However, all of these patents describe circuits which perform multiple multiplications serially, thereby inherently limiting the speed at which the dot product of large dimensional vectors can be calculated. See also A. Weinberger, "Multiplier Decoding with Look-Ahead", IBM Technical Disclosure Bulletin, Vol. 20, No. 9, February, 1978, pp. 3591-3593 and T. Jayashree and D. Basu, "On Binary Multiplication Using Quarter Square Algorithm", IEEE Transactions on Computers, September, 1976, pp. 957-960. See also U. S. Pat. No. 3,732,409 of Fletcher et al. and "Digital Logic Fundamentals", pp. 388-392, by Thomas L. Floyd, 1977, Charles E. Merrill Publishing Company.
In my U.S. Pat. No. 4,884,232 granted November 28, 1989, I disclose a digital circuit for executing a parallel algorithm to compute the dot product of large dimensional vectors at very high speed. The circuit may be made of a plurality of cascaded 1-bit correlator chips and a plurality of arithmetic logic unit (ALU) chips that sum the outputs of the correlator chips. I also disclose in that patent a general purpose computer architecture for implementing the parallel algorithm.
Two's complement has become a standard today in the computer field for representing positive and negative values. Analog-to-digital (A/D) converters are available today with a two's complement output. It would therefore be desirable to provide an approach for high speed calculation of the dot product of large dimensional vectors in two's complement representation.